home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / BBS-Archive / Comm / AmiTCP30b2.lha / src / util / ls / sort.c < prev    next >
C/C++ Source or Header  |  1994-02-24  |  3KB  |  117 lines
  1. /* $Id: sort.c,v 1.1 1993/09/17 06:24:05 ppessi Exp $
  2.  * 
  3.  * sort.c -- sort a table using quicksort
  4.  * 
  5.  *  Author: ppessi <Pekka.Pessi@hut.fi>
  6.  * 
  7.  *  Copyright (c) 1992 Pekka Pessi
  8.  *                     All rights reserved
  9.  * 
  10.  * Created      : Thu Dec  3 11:21:42 1992 ppessi
  11.  * Last modified: Thu Dec  3 11:57:51 1992 ppessi
  12.  *  
  13.  */
  14.  
  15. #ifdef NOMYDEBUG
  16. #define MYDEBUG( x )
  17. #else
  18. #include <clib/dos_protos.h>
  19. #define MYDEBUG(x) x
  20. #endif
  21.  
  22. static void 
  23.   _quick_sort(void *slots[], int left, int right, int(*compare)(void *, void *))
  24. {
  25.   void *ld, *rd, *md, *sd;
  26.   int middle, l, r;
  27.  
  28.   remove_tail:
  29.   if (right - left < 8)        /* we left this for insertion sort */
  30.     return;
  31.   /* Find median */
  32.   middle = (left + right) / 2;
  33.   ld = slots[left];
  34.   md = slots[middle];
  35.   rd = slots[right];
  36.  
  37.   MYDEBUG( FPrintf(Stderr, 
  38.            "Left (%ld): %s, middle (%ld): %s, right (%ld): %s\n", 
  39.           left, ld -> ed_Name, 
  40.            middle, md -> ed_Name, 
  41.           right, rd -> ed_Name) );
  42.  
  43.   if ((compare)(ld, rd) > 0) 
  44.     sd = rd,  rd = ld,  ld = sd; /* swap */
  45.  
  46.   if ((compare)(ld, md) > 0) 
  47.     sd = md,  md = ld,  ld = sd; /* swap */
  48.  
  49.   if ((compare)(md, rd) > 0) 
  50.     sd = md,  md = rd,  rd = sd; /* swap */
  51.  
  52.   slots[right] = rd;        
  53.   slots[middle] = slots[right - 1];
  54.   slots[left] = ld;
  55.   /* use median as a sentinel and partitioning element */
  56.   slots[right - 1] = md;    
  57.  
  58.   MYDEBUG( FPrintf(Stderr, "Left: %s, middle:  %s, right: %s\n", 
  59.           ld -> ed_Name, md -> ed_Name, rd -> ed_Name) );
  60.  
  61.   for (l = left, r = right - 1; l < r; ) {    
  62.     /* scan from left */
  63.     do {l++;} while ((compare)(md, slots[l]) >= 0);
  64.  
  65.     MYDEBUG( FPrintf(Stderr, "Left %s \n", slots[l] -> ed_Name) );
  66.     /* scan from right */
  67.     do {r--;} while ((compare)(slots[r], md) >= 0);
  68.  
  69.     MYDEBUG( FPrintf(Stderr, "Right %s \n", slots[r] -> ed_Name) );
  70.  
  71.     if (l < r)
  72.       ld = slots[l], slots[l] = slots[r], slots[r] = ld; /* swap elements */
  73.   }
  74.   /* move partition element into partition place */
  75.   md = slots[right - 1], slots[right - 1] = slots[l], slots[l] = md;
  76.  
  77.   if (l > middle) {        /* sort smaller partition recursively */
  78.     _quick_sort(slots, l + 1, right, compare);
  79.     right = l - 1;
  80.   } else {
  81.     _quick_sort(slots, left, l - 1, compare);
  82.     left = l + 1;
  83.   }
  84.   goto remove_tail;            /* remove tail recursion  */
  85. }
  86.  
  87. /*
  88.   Actual quick_sort does final sorting with insertion sort
  89. */
  90. void
  91. quick_sort(void *slots[], int size, int(*compare)(void *, void *))
  92. {
  93.   register int i, j;
  94.   MYDEBUG( register int distance; )
  95.   register void *data;
  96.  
  97.   _quick_sort(slots, 0, size- 1, compare);
  98.  
  99.   for (j = 1; j < size; j++) {
  100.     data = slots[j];
  101.     i = j; 
  102.  
  103.     MYDEBUG( distance = 0; )
  104.  
  105.     while (i > 0 && (compare)(data, slots[i-1]) < 0) {
  106.       slots[i] = slots[i-1];
  107.       i--; 
  108.  
  109.       MYDEBUG( distance++; )
  110.     }
  111.     slots[i] = data;
  112.     MYDEBUG( if (distance)
  113.         FPrintf(Stderr, "Moved %s by %ld\n", data -> ed_Name, distance); )
  114.   }
  115. }
  116.  
  117.